Robotic and automated processes are well known in the art. In manufacturing industries, automated processes are used to manufacture everything from automobiles to computer circuit boards. When designing an assembly line in a manufacturing process, it is often desirable to create a computer model of the manufacturing line and processes prior to actual construction. To this end, computer aided drafting (CAD) has been an invaluable tool. CAD allows a draftsperson to create a three-dimensional computer model of a manufacturing line, including the processes and the various machines required to implement those processes. However, CAD is limited in that it does not depict dynamic processes with great precision or accuracy. In other words, the CAD software has problems depicting the dynamic movement of the machines in the manufacturing environment and even greater problems determining if the various machines will collide with one another. Moreover, when multiple dynamic processes are implemented, the processing capacity and memory required to simulate the dynamic manufacturing process is often prohibitive.
In large manufacturing environments, like automobile manufacturing, there is usually sufficient space to give each robotic machine its own working radius such that it is impossible for one machine to collide with the other machines. FIG. 1 is a plan view illustration of such a manufacturing environment. In FIG. 1, the manufacturing line is depicted running left to right through four manufacturing processes. Each process comprises at least one arm which has a working radius. The working radius is defined as the maximum extendable reach of any one machine. The working radius of a machine is usually, but not necessarily, cylindrical or spherical, depending on the type of machine. The working radii are specific to each machine and may differ from one machine to another. In FIG. 1, the working radii of the various machines do not overlap, thus it is impossible for the arm of any one machine to physically collide with the arm of any other machine.
However, when space is limited or the manufactured device is smaller, as in circuit board manufacturing, the individual machines must be closer together so that the working radii overlap. FIG. 2 is a plan view illustration of a manufacturing line running left to right with ten machines accessing the line. Because it is very undesirable for the machines to physically collide with one another, the manufacturing process layout must be designed such that the individual machines are able to freely move about and perform their individual processes, yet not collide with or impede the processes of the other machines. Thus, a computer program must determine where the arm of each machine will be at a given time and arrange the processes so that the arms of the machines never attempt to occupy the same space at the same time.
To further complicate the matter, the individual machines are not usually of the same height, a quality not illustrated in FIG. 1 or 2. The differing height allows the machines to be placed even closer together so that the manufacturing line can be even further shortened. Thus, it is possible for the arm of one machine to be physically above the arm of another machine and yet the two arms will not collide. The addition of a third dimension of analysis to the design layout problem makes the solution extremely computationally intensive given traditional methods of analysis.
Automated processes are also used in environments other than manufacturing. For example, automated processes are frequently used to unload cargo from the space shuttle. FIG. 3 is an illustration of the space shuttle with the robotic arm. Because it is very desirable to avoid collisions between the cargo and the shuttle during unloading, the unloading algorithm for the robotic arm is pre-programmed so that the astronauts do not have to manually control the robotic arm. Automated unloading instructions allow the astronauts more time to perform other tasks and decrease the likelihood of damaging the shuttle or the cargo. A similar algorithm can also be used to determine if a collision will occur between any two objects in a multitude of other environments. For example, is advantageous to know if two objects will collide in air traffic control industry (i.e. to prevent collisions). It is also important to know if two objects will collide when developing programming software for missile defense systems (i.e. to ensure a collision). Therefore, a need exists for a computationally efficient method of determining whether a plurality of objects will collide.
The prior art has frequently addressed the problem of determining whether two objects will collide. U.S. Pat. No. 5,812,138 entitled “Method and Apparatus for Dynamic Object Identification After Z-Collision” discloses a method of determining if two three-dimensional objects have collided in three-dimensional space. The method disclosed in the '138 patent maps out the surface of a plurality of three-dimensional objects and determines if they collide. While the surface mapping technique disclosed in the '138 patent is useful for simple three-dimensional objects, it becomes computationally intensive for complex three-dimensional objects because the computer has to recalculate the location of every pixel for every time interval to determine if the two objects have collided. Thus, a less computationally intensive model is needed to determine if two complex three-dimensional objects will collide.
U.S. Pat. No. 6,004,016 entitled “Motion Planning and Control for Systems with Multiple Mobile Objects” discloses a computational method for generating movement paths and avoiding collisions amongst a plurality of jointed robot assembly arms. The method disclosed in the '016 patent involves defining the three-dimensional space around the manipulator arms in terms a multiplicity of cells and defining the movement of the arm in terms of the cells that the arm occupies at a given time. By knowing which cells are occupied by the arms at a given time, you can determine if more than one arm is attempting to occupy a cell at any given time and, thus, whether the arms will collide. Unfortunately, in close assembly situations like circuit board manufacturing, the method in the '016 is not very practical because the various assembly machines work in extremely close proximity to each other and thus the cells size would have to be very small. Use of smaller cell sizes significantly increases the number of computations resulting in a computationally intensive computer program. Therefore, a need exists for a different method of determining whether two separate three-dimensional bodies will collide.
U.S. Pat. No. 4,578,757 entitled “Method for Preventing Collision of Two Mutually Movable Bodies and an Apparatus Including an Arrangement for Preventing Collision” discloses a method of determining if two complex three-dimensional bodies will collide. The method disclosed in the '757 patent defines the two objects in terms of numerous spheres. The spheres completely encase the objects; however the objects do not completely fill the spheres. A computational method is then disclosed for determining if any of the spheres intersect. The sphere method inherently overcompensates for the displacement of flat surfaces by creating a series of hemispherical subsurfaces not occupied by the object. This hemispherical space can be reduced by creating additional spheres; however this in turn increases the number and intensity of the computations. Therefore, a less computational intense method of determining whether two complex three-dimensional bodies will collide is needed.
Consequently, a need exists for a more computationally efficient method of simulating dynamic movement of a plurality of complex three-dimensional objects. A need further exists for a method of determining if a plurality of moving complex three-dimensional objects will collide with other moving complex three-dimensional objects. Additionally, the need extends to an apparatus and method that is less computationally intensive than the prior art solutions.